37. Sudoku Solver
Hard

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:


 

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.
Accepted
245,566
Submissions
510,352
Seen this question in a real interview before?
Similar Questions

Average Rating: 4.25 (40 votes)

Premium

Solution


Approach 0: Brute Force

The first idea is to use brut-force to generate all possible ways to fill the cells with numbers from 1 to 9, and then check them to keep the solution only. That means 9819^{81} operations to do, where 99 is a number of available digits and 8181 is a number of cells to fill. Hence we're forced to think further how to optimize.


Approach 1: Backtracking

Conceptions to use

There are two programming conceptions here which could help.

The first one is called constrained programming.

That basically means to put restrictions after each number placement. One puts a number on the board and that immediately excludes this number from further usage in the current row, column and sub-box. That propagates constraints and helps to reduce the number of combinations to consider.

bla

The second one called backtracking.

Let's imagine that one has already managed to put several numbers on the board. But the combination chosen is not the optimal one and there is no way to place the further numbers. What to do? To backtrack. That means to come back, to change the previously placed number and try to proceed again. If that would not work either, backtrack again.

bla

How to enumerate sub-boxes

One tip to enumerate sub-boxes: let's use box_index = (row / 3) * 3 + column / 3 where / is an integer division.

Algorithm

Now everything is ready to write down the backtrack function backtrack(row = 0, col = 0).

  • Start from the upper left cell row = 0, col = 0. Proceed till the first free cell.

  • Iterate over the numbers from 1 to 9 and try to put each number d in the (row, col) cell.

    • If number d is not yet in the current row, column and box :

      • Place the d in a (row, col) cell.
      • Write down that d is now present in the current row, column and box.
      • If we're on the last cell row == 8, col == 8 :
        • That means that we've solved the sudoku.
      • Else
        • Proceed to place further numbers.
      • Backtrack if the solution is not yet here : remove the last number from the (row, col) cell.

Implementation

Complexity Analysis

  • Time complexity is constant here since the board size is fixed and there is no N-parameter to measure. Though let's discuss the number of operations needed : (9!)9(9!)^9. Let's consider one row, i.e. not more than 99 cells to fill. There are not more than 99 possibilities for the first number to put, not more than 9×89 \times 8 for the second one, not more than 9×8×79 \times 8 \times 7 for the third one etc. In total that results in not more than 9!9! possibilities for a just one row, that means not more than (9!)9(9!)^9 operations in total. Let's compare:

    • 981=1966270504755529136180759085269121162831034509442147669273154155379663911968099^{81} = 196627050475552913618075908526912116283103450944214766927315415537966391196809 for the brute force,

    • and (9!)9=109110688415571316480344899355894085582848000000000(9!)^9 = 109110688415571316480344899355894085582848000000000 for the standard backtracking, i.e. the number of operations is reduced in 102710^{27} times !

  • Space complexity : the board size is fixed, and the space is used to store board, rows, columns and boxes structures, each contains 81 elements.

Report Article Issue

Comments: 22
haoyangfan's avatar
Read More

Share a simplified version of backtrack solution:

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)

        rows, cols, boxes = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set)

        for r in range(n):
            for c in range(n):
                if board[r][c] == '.':
                    continue

                v = int(board[r][c])
                rows[r].add(v)
                cols[c].add(v)
                boxes[(r // 3) * 3 + c // 3].add(v)


        def is_valid(r, c, v):
            box_id = (r // 3) * 3 + c // 3
            return v not in rows[r] and v not in cols[c] and v not in boxes[box_id]


        def backtrack(r, c):
            if r == n - 1 and c == n:
                return True
            elif c == n:
                c = 0
                r += 1

            # current grid has been filled
            if board[r][c] != '.':
                return backtrack(r, c + 1)

            box_id = (r // 3) * 3 + c // 3
            for v in range(1, n + 1):
                if not is_valid(r, c, v):
                    continue

                board[r][c] = str(v)
                rows[r].add(v)
                cols[c].add(v)
                boxes[box_id].add(v)

                if backtrack(r, c + 1):
                    return True

                # backtrack
                board[r][c] = '.'
                rows[r].remove(v)
                cols[c].remove(v)
                boxes[box_id].remove(v)

            return False


        backtrack(0, 0)

28
Show 1 reply
Reply
Share
Report
ShaneTsui's avatar
Read More

There's no need creating extra data structure as rows, columns and boxes. It's good for engineering, but not practical for interview. Here's a succint version of backtracing

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # Check if num can be placed at board[i][j]
        def can_place(i, j, num):
            # Check row
            if any(num == n for n in board[i]):
                return False
            
            # Check col
            if any(num == n for n in list(zip(*board))[j]):
                return False
            
            # Check box
            start_row, start_col = (i // 3) * 3, (j // 3) * 3
            for r in range(start_row, start_row + 3):
                for c in range(start_col, start_col + 3):
                    if num == board[r][c]:
                        return False
            return True
        
        def find_unassigned():
            for r in range(len(board)):
                for c in range(len(board[0])):
                    if board[r][c] == '.':
                        return r, c
            return -1, -1
        
        def solve():
            r, c = find_unassigned()
            
            if r == -1 and c == -1:
                return True
            
            for num in [str(n) for n in range(1, 10)]:
                if can_place(r, c, num):
                    board[r][c] = num
                    if solve():
                        return True
                    board[r][c] = '.'
            return False
		
        if not board:
            return
        solve()

32
Show 4 replies
Reply
Share
Report
LPEO's avatar
Read More

For simplicity during an interview

Time Complexity: O(9^(m * n))
Space Complexity: O(m*n)

18
Show 3 replies
Reply
Share
Report
zhang-peter's avatar
Read More

i have three times faster java code(3 ms), what i do is first fill the cells which can only fill one number:

class Solution {
    // box size
    int n = 3;
    // row size
    int N = n * n;

    int [][] rows = new int[N][N + 1];
    int [][] columns = new int[N][N + 1];
    int [][] boxes = new int[N][N + 1];

    char[][] board;

    boolean sudokuSolved = false;

    public boolean couldPlace(int d, int row, int col) {
        /*
        Check if one could place a number d in (row, col) cell
        */
        int idx = (row / n ) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }

    public boolean couldPlaceOnlyOne( int row, int col) {
        /*
        Check if one could only place one number in (row, col) cell
        */
        int place = 0, count = 0;
        for (int d = 1; d < 10; d++) {
            int idx = (row / n ) * n + col / n;
            if (rows[row][d] + columns[col][d] + boxes[idx][d] == 0) {
                count += 1;
                place = d;
            }
        }
        if (count == 1) {
            placeNumber(place, row, col);
        }
        return false;
    }

    public void placeNumber(int d, int row, int col) {
        /*
        Place a number d in (row, col) cell
        */
        int idx = (row / n ) * n + col / n;

        rows[row][d]++;
        columns[col][d]++;
        boxes[idx][d]++;
        board[row][col] = (char)(d + '0');
    }

    public void removeNumber(int d, int row, int col) {
        /*
        Remove a number which didn't lead to a solution
        */
        int idx = (row / n ) * n + col / n;
        rows[row][d]--;
        columns[col][d]--;
        boxes[idx][d]--;
        board[row][col] = '.';
    }

    public void placeNextNumbers(int row, int col) {
        /*
        Call backtrack function in recursion
        to continue to place numbers
        till the moment we have a solution
        */
        // if we're in the last cell
        // that means we have the solution
        if ((col == N - 1) && (row == N - 1)) {
            sudokuSolved = true;
        }
        // if not yet
        else {
            // if we're in the end of the row
            // go to the next row
            if (col == N - 1) backtrack(row + 1, 0);
            // go to the next column
            else backtrack(row, col + 1);
        }
    }

    public void backtrack(int row, int col) {
        /*
        Backtracking
        */
        // if the cell is empty
        if (board[row][col] == '.') {
            // iterate over all numbers from 1 to 9
            for (int d = 1; d < 10; d++) {
                if (couldPlace(d, row, col)) {
                    placeNumber(d, row, col);
                    placeNextNumbers(row, col);
                    // if sudoku is solved, there is no need to backtrack
                    // since the single unique solution is promised
                    if (!sudokuSolved) removeNumber(d, row, col);
                }
            }
        } else placeNextNumbers(row, col);
    }

    public void solveSudoku(char[][] board) {
        this.board = board;

        // init rows, columns and boxes
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                char num = board[i][j];
                if (num != '.') {
                    int d = Character.getNumericValue(num);
                    placeNumber(d, i, j);
                }
            }
        }
        while (true) {
            int flag = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == '.') {
                        if (couldPlaceOnlyOne(i, j) == true) {
                            flag = 1;
                        }
                    }
                }
            }
            if (flag == 0) {
                break;
            }

        }
        backtrack(0, 0);
    }
}

4
Show 1 reply
Reply
Share
Report
brokechigga's avatar
Read More

why this code only work in python 3 not 2?

2
Show 2 replies
Reply
Share
Report
ruifeng's avatar
Read More

I think the operations analysis is wrong. Even the second number has 8 possible candidates, you're still trying to fill from 1-9 for every position. You're not eliminating any number when trying to fill. So I'd say the operation should be 9 ^ (9 * 9)

2
Show 2 replies
Reply
Share
Report
lenchen1112's avatar
Read More

Clean Python3, dfs by row-based.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_block_valid(i: int, j: int) -> bool:
            nums = [board[r][c] for r in range(i-2, i+1) for c in range(j-2, j+1)]
            return len(nums) == len(set(nums))

        def dfs(i: int, j: int, row: set = None) -> bool:
            if i == 9: return True
            if j == 9: return dfs(i+1, 0)
            if i % 3 == 2 and j % 3 == 2 and not is_block_valid(i, j): return False
            if j == 0: row = {str(i) for i in range(1, 10)} - set(board[i])
            if board[i][j] != '.': return dfs(i, j+1, row)
            if row:
                for num in row & cols[j]:
                    board[i][j] = num
                    cols[j].discard(num)
                    row.discard(num)
                    if dfs(i, j+1, row): return True
                    cols[j].add(num)
                    row.add(num)
                board[i][j] = '.'
            return False

        used_cols = [set(row[j] for row in board) for j in range(9)]
        cols = [{str(i) for i in range(1, 10)} - nums for nums in used_cols]
        dfs(0, 0)

1
Reply
Share
Report
wds8807's avatar
Read More

Why two functions are calling each other?

0
Show 1 reply
Reply
Share
Report
zhang-peter's avatar
Read More

i have three times faster python code(80 ms), what i do is first fill the cells which can only fill one number:

from collections import defaultdict


class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def could_place(d, row, col):
            """
            Check if one could place a number d in (row, col) cell
            """
            return not (d in rows[row] or d in columns[col] or
                        d in boxes[box_index(row, col)])

        def place_number(d, row, col):
            """
            Place a number d in (row, col) cell
            """
            rows[row][d] += 1
            columns[col][d] += 1
            boxes[box_index(row, col)][d] += 1
            board[row][col] = str(d)

        def remove_number(d, row, col):
            """
            Remove a number which didn't lead 
            to a solution
            """
            del rows[row][d]
            del columns[col][d]
            del boxes[box_index(row, col)][d]
            board[row][col] = '.'

        def could_place_only_one(row, col):
            # if only a number can file in the cell, fill it.
            count = []
            for d in range(1, 10):
                if could_place(d, row, col):
                    count.append(d)
            if len(count) == 1:
                place_number(count[0], row, col)
                return True
            return False

        def firstcheck():
            while 1:
                flag = 0
                for i in range(N):
                    for j in range(N):
                        if board[i][j] == '.' and could_place_only_one(i, j) == True:
                            flag = 1
                if flag == 0:
                    break

        def place_next_numbers(row, col):
            """
            Call backtrack function in recursion
            to continue to place numbers
            till the moment we have a solution
            """
            # if we're in the last cell
            # that means we have the solution
            if col == N - 1 and row == N - 1:
                nonlocal sudoku_solved
                sudoku_solved = True
            # if not yet
            else:
                # if we're in the end of the row
                # go to the next row
                if col == N - 1:
                    backtrack(row + 1, 0)
                # go to the next column
                else:
                    backtrack(row, col + 1)

        def backtrack(row=0, col=0):
            """
            Backtracking
            """
            # if the cell is empty
            if board[row][col] == '.':
                # iterate over all numbers from 1 to 9
                for d in range(1, 10):
                    if could_place(d, row, col):
                        place_number(d, row, col)
                        place_next_numbers(row, col)
                        # if sudoku is solved, there is no need to backtrack
                        # since the single unique solution is promised
                        if not sudoku_solved:
                            remove_number(d, row, col)
            else:
                place_next_numbers(row, col)

        # box size
        n = 3
        # row size
        N = n * n
        # lambda function to compute box index

        def box_index(row, col): return (row // n) * n + col // n

        # init rows, columns and boxes
        rows = [defaultdict(int) for i in range(N)]
        columns = [defaultdict(int) for i in range(N)]
        boxes = [defaultdict(int) for i in range(N)]
        for i in range(N):
            for j in range(N):
                if board[i][j] != '.':
                    d = int(board[i][j])
                    place_number(d, i, j)

        sudoku_solved = False
        firstcheck()
        backtrack()

0
Show 1 reply
Reply
Share
Report
tryc14's avatar
Read More

it also makes sense to precalculate the empty indexes and then using the index for backtracking and not to calculate the next empty index every time

def backtrack(curr_idx)
    if curr_idx == len(empty_spaces):
                return board
    curr_row, curr_col = empty_spaces[curr_idx]
    ....
    for digit in range(1, 10):
                board[curr_row][curr_col] = str(digit)
                if self.validate_move(board, curr_row, curr_col):
                    solved = backtrack(curr_idx + 1)
                    ....

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.